package tree.binarysearchtree;

import linkedlist.ListNode;
import tree.TreeNode;

/**
 * @Classname : ConvertSortedListToBinarySearchTree
 * @Description :
 * <a href="https://leetcode.cn/problems/convert-sorted-list-to-binary-search-tree/">109. 有序链表转换二叉搜索树</a>
 * @Author : chentianyu
 * @Date 2023/1/26 16:57
 */


public class ConvertSortedListToBinarySearchTree {
    /**
     * 有序链表递归转化二叉搜索树
     *
     * @param head
     * @return
     */
    public TreeNode sortedListToBST(ListNode head) {
        if (head == null) return null;

        ListNode[] deal = deal(head);
        TreeNode root = new TreeNode(deal[1].val);
        root.left = sortedListToBST(deal[0]);
        root.right = sortedListToBST(deal[2]);
        return root;
    }


    /**
     * 处理链表找到中点
     *
     * @param head
     * @return [左链表, 中点, 右链表]
     */
    private ListNode[] deal(ListNode head) {
        if (head.next == null) return new ListNode[]{null, head, null};

        ListNode fast = head, slow = head, preSlow = null;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            preSlow = slow;
            slow = slow.next;
        }
        preSlow.next = null;
        return new ListNode[]{head, slow, slow.next};
    }
}
